package com.chapter4.graph.sp;

import java.util.Stack;

import org.junit.Test;

import com.util.Constants;
import com.util.In;

public class TestSP {

	@Test
	public void testSP() {
		In in = new In(Constants.dirPath + "tinyEWD.txt");
		DirectWeightGraph g = new DirectWeightGraph(in);
		int s = 0;
		DijkstraSP sp = new DijkstraSP(g, s);

		for (int i = 0; i < g.V(); i++) {
			if (sp.hasPathTo(i)) {
				System.out.print(s + "到" + i + "最短路径长度为：" + sp.distTo(i) + " ");
				Stack<DirectEdge> edge = (Stack<DirectEdge>) sp.pathTo(i);
				while (!edge.isEmpty())
					System.out.print(edge.pop() + " ");
				System.out.println();
			} else {
				System.out.println(s + "到" + i + "无路径");
			}
		}
	}
	
	@Test
	public void testTop(){
		In in = new In(Constants.dirPath + "tinyEWDAG.txt");
		DirectWeightGraph g = new DirectWeightGraph(in);
		Topological top=new Topological(g);
		
		for(int w:top.topOrder()){
			System.out.print(w+" ");
		}
	}
	
	@Test
	public void testDirectedCycle(){
		In in=new In("F:\\算法\\attach\\tinyEWD.txt");
		DirectWeightGraph d=new DirectWeightGraph(in);
		DirectWeightCycle dc=new DirectWeightCycle(d);
		System.out.println(dc.hasCycle());
		Stack<Integer> cycle=(Stack<Integer>) dc.cycle();
		while(!cycle.isEmpty()){
			System.out.print(cycle.pop()+"->");
		}
	}
	
	@Test
	public void test1(){
		DirectEdge[] e=new DirectEdge[5];
		System.out.println(e[0]);
	}
	
	@Test
	public void testAcyclicSP(){
		In in = new In(Constants.dirPath + "tinyEWDAG.txt");
		DirectWeightGraph g = new DirectWeightGraph(in);
		int s=5;
		AcyclicSP sp=new AcyclicSP(g, s);
		for(int i=0;i<g.V();i++){
			if (sp.hasPathTo(i)) {
				System.out.print(s + "到" + i + "最短路径长度为：" + sp.distTo(i) + " ");
				for (DirectEdge edge:sp.pathTo(i))
					System.out.print(edge + " ");
				System.out.println();
			} else {
				System.out.println(s + "到" + i + "无路径");
			}
		}
	}
	
	@Test
	public void testBSP(){
		In in = new In(Constants.dirPath + "tinyEWD.txt");
		DirectWeightGraph g = new DirectWeightGraph(in);
		int s=0;
		BellmanFordSP sp=new BellmanFordSP(g, s);
		for(int i=0;i<g.V();i++){
			if (sp.hasPathTo(i)) {
				System.out.print(s + "到" + i + "最短路径长度为：" + sp.distTo(i) + " ");
				for (DirectEdge edge:sp.pathTo(i))
					System.out.print(edge + " ");
				System.out.println();
			} else {
				System.out.println(s + "到" + i + "无路径");
			}
		}
	}
}
